public class Main {
    /**
     * 删除链表的倒数第N个节点
     * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     */
    public static void main(String[] args) {
        System.out.println("hello world >_O");
        ListNode head = new ListNode();
        head.val = 1;
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ListNode answer = new Main().removeNthFromEnd(head, 2);
        while (answer != null) {
            System.out.println(answer.val);
            answer = answer.next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode slow = dummyHead;
        ListNode fast = dummyHead;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 往后多加一次，让慢指针指向删除结点的前一个结点，方便删除
        fast = fast.next;

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 删除
        slow.next = slow.next.next;

        return dummyHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }
}
